//	 ID : pallab81
// 	PROG : 910
// 	LANG : C++
// 	2011-10-13-19.51.30 Thursday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define fo(i,ed) for(int i = 0 ; i < ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

inline void wait( double seconds ){
    double endtime = clock()+( seconds* CLOCKS_PER_SEC );
    while( clock() < endtime ){
        ;
    }
}

int N,moves;
vector< pair<int,int> > cango;
int special[ 30 ] ;
Int dp[28][32];

inline void Read(){
    cango.assign(N+5,mk(0,0));
    SET(special,-1);
    char a,b,c,d;
    fo(i,N){
        cin>>a>>b>>c>>d;
        int u = a-'A';
        int v1 = b-'A';
        int v2 = c-'A';
        cango[u] =  mk(v1,v2) ;
        if( d=='x' ){
            special[u]=1;
        }
    }
    scanf("%d",&moves);
}

inline Int go(int u, int cur_move){
    if( cur_move==0 ){
        return  special[u]!=-1 ? (Int)1 : (Int)0 ;
    }
    Int &res = dp[u][cur_move];
    if( res!=-1 ){
        return res;
    }
    res=0;
    int v1 = cango[u].f;
    int v2 = cango[u].s;

    Int var1 = go(v1,cur_move-1);
    Int var2 = go(v2,cur_move-1);

    res = var1 + var2 ;

return res;
}

inline void Proc(){
    SET(dp,-1);
    Int var = go(0,moves);
    cout<<var<<"\n";
}

int main(){
	#ifndef ONLINE_JUDGE
		freopen("in","rt",stdin);
	#endif

        while( scanf("%d",&N)==1  ){
            Read();
            Proc();
        }


return 0;
}
